#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
// 最长定差子序列：https://leetcode.cn/problems/longest-arithmetic-subsequence-of-given-difference/description/
using namespace std;
class Solution {
public:
    int longestSubsequence(vector<int>& arr, int difference) {
        int n=arr.size();
        unordered_map<int,int> hash;
        hash[arr[0]]=0;
        vector<int> dp(n,1);
        int ret=1;
        for(int i=1;i<n;i++)
        {
            auto pos=hash.find(arr[i]-difference);
            if(pos!=hash.end())
                dp[i]=max(dp[i],dp[pos->second]+1);
            hash[arr[i]]=i;
            ret=max(ret,dp[i]);
        }
        return ret;
    }
};